home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / cmds / dvips / repack.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-01-05  |  14.1 KB  |  468 lines
  1. /*
  2.  *   Compressed TeX fonts in PostScript.  Copyright (C) 1989
  3.  *   by Radical Eye Software.  All Rights Reserved.
  4.  *   (Slight mods by Don Knuth in December 89.)
  5.  */
  6. #include "structures.h" /* The copyright notice in that file is included too! */
  7. #ifdef DEBUG
  8. extern integer debug_flag;
  9. #endif /* DEBUG */
  10.  
  11. /*   Given a raster that has been unpacked from PK format,
  12.  *   we compress it by another scheme that is suitable for
  13.  *   a PostScript-oriented unpacking. We write instructions for
  14.  *   a little interpreter whose one-byte instructions have the form
  15.  *   18*opcode+parameter. The interpreter forms each row based
  16.  *   on simple transformations to the previous row. */
  17.  
  18. #define MAXOUT (18)
  19. #define CMD(n) (MAXOUT*(n))
  20. #define ADVXCHG1 CMD(0)
  21. #define ADVXCHG1END CMD(1)
  22. #define CHGX CMD(2)-1
  23. #define CHGXEND CMD(3)-1
  24. #define ADVXLSH CMD(4)
  25. #define ADVXLSHEND CMD(5)
  26. #define ADVXRSH CMD(6)
  27. #define ADVXRSHEND CMD(7)
  28. #define ADVX CMD(8)-1
  29. #define REPX CMD(9)-1
  30. #define SETX CMD(10)-1
  31. #define CLRX CMD(11)-1
  32. #define ADVXCHG2 CMD(12)
  33. #define ADVXCHG2END CMD(13)
  34. #define END CMD(14)
  35.  
  36. extern char *malloc() ;
  37. extern free() ;
  38. extern void error() ;
  39. extern long getlong() ;
  40. extern long unpack() ;
  41.  
  42. static int rowlength = 0 ;
  43. static unsigned char *specdata ;
  44. static long tslen = 0 ;
  45. static unsigned char *tempstore, *tsp, *tsend ;
  46.  
  47. /* First, a routine that appends one byte to the compressed output. */
  48.  
  49. #define addtse(n) {lcm=tsp-tempstore;addts(n);} /* mark END option position */
  50.  
  51. static long addts(what)
  52. register unsigned char what ;
  53. {
  54.    register unsigned char *p, *q ;
  55.  
  56.    if (tsp >= tsend) {
  57.       if (tempstore == NULL) {
  58.          tslen = 4096 ;
  59.          tempstore = (unsigned char *)malloc((unsigned)tslen) ;
  60.          if (tempstore == NULL)
  61.             error("! out of memory") ;
  62.          tsp = tempstore ;
  63.       } else {
  64.          tslen = 2 * tslen ;
  65.          tsp = (unsigned char *)malloc((unsigned)tslen) ;
  66.          if (tsp == NULL)
  67.             error("! out of memory") ;
  68.          for (p=tempstore, q=tsp; p<tsend; p++, q++)
  69.             *q = *p ;
  70.          free((char *)tempstore) ;
  71.          tempstore = tsp ;
  72.          tsp = q ;
  73.       }
  74.       tsend = tempstore + tslen ;
  75.    }
  76.    *tsp++ = what ;
  77. }
  78.  
  79. /* Next, a routine that discovers how to do the compression. */
  80.  
  81. #define rsh(a,b) ( ((a)==0) ? ((b)==128) : ( ((a)==255) ? ((b)==127) :\
  82.                                     ((b)==(((a)>>1)|((a)&128))) ))
  83. #define lsh(a,b) ( ((a)==0) ? ((b)==1) : ( ((a)==255) ? ((b)==254) :\
  84.                                     ((b)==((((a)<<1)&255)|((a)&1))) ))
  85. #define DIFFERENT (1)
  86. #define LSHPOSSIB (2)
  87. #define RSHPOSSIB (4)
  88. #define BLKPOSSIB (8)
  89. #define WHTPOSSIB (16)
  90. #define ENDROW (32)
  91. #define NOPOSSIB(n) ((n&(LSHPOSSIB|RSHPOSSIB|BLKPOSSIB|WHTPOSSIB))==0)
  92. #define NOSHIFT(n) ((n&(LSHPOSSIB|RSHPOSSIB))==0)
  93. /*
  94.  *   Our input bytes are packed to the 16-bit word.  On output,
  95.  *   they're packed to bytes. Thus, we may have to skip a byte at
  96.  *   the end of each row.
  97.  */
  98. void dochar(from, width, height)
  99. unsigned char *from ;
  100. short width, height ; /* in bytes */
  101. {
  102.    register int i ;
  103.    register unsigned char *f, *t, *d ;
  104.    register unsigned char *e ;
  105.    register int accum ;
  106.    int j, k ;
  107.    int diffrow ;
  108.    int repeatcount ;
  109.    int lit, pos, cmd ;
  110.    long lcm ;
  111.    int widthc ;
  112.  
  113.    widthc = width + (width & 1) ; /* halfword correction */
  114.    lcm = -1 ;
  115.    if (width > rowlength) {
  116.       if (rowlength)
  117.          free((char *)specdata) ;
  118.       rowlength = 2 * widthc ;
  119.       specdata = (unsigned char *)malloc((unsigned)(rowlength + 1)) ;
  120.       if (specdata == NULL)
  121.          error("! out of memory") ;
  122.    }
  123.    for (i=0, t=specdata; i<widthc; i++, t++)
  124.       *t = 0 ;
  125.    f = specdata ;
  126.    repeatcount = 0 ;
  127.    for (j=0; j<height; j++, f = from, from += widthc) {
  128.       diffrow = 0 ;
  129.       for (i=0, t=from, d=specdata; i<width; i++, f++, t++, d++) {
  130.          if (*f == *t) {
  131.             if (*t == 0)
  132.                *d = WHTPOSSIB ;
  133.             else if (*t == 255)
  134.                *d = BLKPOSSIB ;
  135.             else
  136.                *d = 0 ;
  137.          } else {
  138.             accum = DIFFERENT ;
  139.             if (rsh(*f, *t))
  140.                accum |= RSHPOSSIB ;
  141.             else if (lsh(*f, *t))
  142.                accum |= LSHPOSSIB ;
  143.             if (*t == 0)
  144.                accum |= WHTPOSSIB ;
  145.             else if (*t == 255)
  146.                accum |= BLKPOSSIB ;
  147.             *d = accum ;
  148.             diffrow++ ;
  149.          }
  150.       } /* end 'for i' */
  151.       *d = ENDROW ;
  152.       if (diffrow == 0) {
  153.          repeatcount++ ;
  154.       } else {
  155.          if (repeatcount) {
  156.             while (repeatcount > MAXOUT) {
  157.                addts((unsigned char)(REPX+MAXOUT)) ;
  158.                repeatcount -= MAXOUT ;
  159.             }
  160.             addts((unsigned char)(REPX+repeatcount)) ;
  161.             repeatcount = 0 ;
  162.          }
  163.          pos = 0 ;
  164.          for (i=0, d=specdata, f=t-width; i<width;) {
  165.             if ((*d & DIFFERENT) == 0) {
  166.                i++ ;
  167.                d++ ;
  168.                f++ ;
  169.             } else {
  170.                accum = 0 ;
  171.                if (pos != i)
  172.                   lit = NOSHIFT(*d) ;
  173.                else /* N.B.: 'lit' does not imply literate programming here */
  174.                   lit = NOPOSSIB(*d) ;
  175.                for (e=d; ;e++) {
  176.                   if (NOPOSSIB(*e))
  177.                      lit = 1 ;
  178.                   if ((*e & DIFFERENT) == 0)
  179.                      break ;
  180.                   if ((*e & WHTPOSSIB) &&
  181.                       (e[1] & WHTPOSSIB)) {
  182.                      while (*e & WHTPOSSIB) {
  183.                         e++ ;
  184.                         accum++ ;
  185.                      }
  186.                      cmd = CLRX ;
  187.                      e -= accum ;
  188.                      break ;
  189.                   } else if ((*e & BLKPOSSIB) &&
  190.                       (e[1] & BLKPOSSIB)) {
  191.                      while (*e & BLKPOSSIB) {
  192.                         e++ ;
  193.                         accum++ ;
  194.                      }
  195.                      cmd = SETX ;
  196.                      e -= accum ;
  197.                      break ;
  198.                   }
  199.                } /* end 'for e'; d pts to first bad byte, e to next good one */
  200.                while (i - pos > MAXOUT) {
  201.                   addts((unsigned char)(ADVX+MAXOUT)) ;
  202.                   pos += MAXOUT ;
  203.                }
  204.                if (k = (e - d)) {
  205.                   if (lit) {
  206.                      if (k > 2) {
  207.                         if (i > pos) {
  208.                            addts((unsigned char)(ADVX + i - pos)) ;
  209.                            pos = i ;
  210.                         }
  211.                         while (k > MAXOUT) {
  212.                            addts((unsigned char)(CHGX + MAXOUT)) ;
  213.                            for (k=0; k<MAXOUT; k++)
  214.                               addts((unsigned char)(*f++)) ;
  215.                            d += MAXOUT ;
  216.                            pos += MAXOUT ;
  217.                            i += MAXOUT ;
  218.                            k -= MAXOUT ;
  219.                         }
  220.                         addtse((unsigned char)(CHGX + k)) ;
  221.                         pos += k ;
  222.                         for (; d<e; d++, i++, f++)
  223.                            addts((unsigned char)(*f)) ;
  224.                      } else {
  225.                         if (k == 1) {
  226.                            if (i == pos+MAXOUT) {
  227.                               addts((unsigned char)(ADVX + MAXOUT)) ;
  228.                               i = pos ;
  229.                            }
  230.                            addtse((unsigned char)(ADVXCHG1 + i - pos)) ;
  231.                            addts((unsigned char)(*f)) ;
  232.                            i++ ;
  233.                            pos = i ;
  234.                            d++ ;
  235.                            f++ ;
  236.                         } else {
  237.                            if (i == pos+MAXOUT) {
  238.                               addts((unsigned char)(ADVX + MAXOUT)) ;
  239.                               i = pos ;
  240.                            }
  241.                            addtse((unsigned char)(ADVXCHG2 + i - pos)) ;
  242.                            addts((unsigned char)(*f)) ;
  243.                            addts((unsigned char)(f[1])) ;
  244.                            i += 2 ;
  245.                            pos = i ;
  246.                            d += 2 ;
  247.                            f += 2 ;
  248.                         }
  249.                      }
  250.                   } else {
  251.                      while (e > d) {
  252.                         if (*d & LSHPOSSIB) {
  253.                            if (i == pos+MAXOUT) {
  254.                               addts((unsigned char)(ADVX + MAXOUT)) ;
  255.                               i = pos ;
  256.                            }
  257.                            addtse((unsigned char)(ADVXLSH + i - pos)) ;
  258.                         } else if (*d & RSHPOSSIB) {
  259.                            if (i == pos+MAXOUT) {
  260.                               addts((unsigned char)(ADVX + MAXOUT)) ;
  261.                               i = pos ;
  262.                            }
  263.                            addtse((unsigned char)(ADVXRSH + i - pos)) ;
  264.                         } else if (*d & WHTPOSSIB) { /* i==pos */
  265.                            addts((unsigned char)(CLRX + 1)) ; lcm = -1 ;
  266.                         } else if (*d & BLKPOSSIB) { /* i==pos */
  267.                            addts((unsigned char)(SETX + 1)) ; lcm = -1 ;
  268.                         } else
  269.                            error("! bug") ; /* why wasn't lit true? */
  270.                         d++ ;
  271.                         f++ ;
  272.                         i++ ;
  273.                         pos = i ;
  274.                      } /* end 'while e>d' */
  275.                   }
  276.                } /* end 'if e>d' */
  277.                if (accum > 0) {
  278.                   if (i > pos) {
  279.                      addts((unsigned char)(ADVX + i - pos)) ;
  280.                      pos = i ;
  281.                   }
  282.                   i += accum ;
  283.                   d += accum ;
  284.                   f += accum ;
  285.                   while (accum > MAXOUT) {
  286.                      addts((unsigned char)(cmd + MAXOUT)) ;
  287.                      accum -= MAXOUT ;
  288.                      pos += MAXOUT ;
  289.                   }
  290.                   lcm = -1 ;
  291.                   addts((unsigned char)(cmd + accum)) ;
  292.                   pos += accum ;
  293.                }
  294.             } /* end 'else DIFFERENT' */
  295.          } /* end 'for i' */
  296.          if (lcm != -1) {
  297.             tempstore[lcm] += MAXOUT ;  /* append END */
  298.             lcm = -1 ;
  299.          } else {
  300.             addts((unsigned char)(END)) ;
  301.          }
  302.       } /* end 'else rows different' */
  303.    } /* end 'for j' */
  304.    if (repeatcount) {
  305.       while (repeatcount > MAXOUT) {
  306.          addts((unsigned char)(REPX+MAXOUT)) ;
  307.          repeatcount -= MAXOUT ;
  308.       }
  309.       addts((unsigned char)(REPX+repeatcount)) ;
  310.       repeatcount = 0 ;
  311.    }
  312. }
  313.  
  314. extern long bytesleft ;
  315. extern quarterword *raster ;
  316. static long mbytesleft ;
  317. static quarterword *mraster ;
  318.  
  319. char *
  320. makecopy(what, len, p)
  321. register unsigned char *what ;
  322. register long len ;
  323. register unsigned char *p ;
  324. {
  325.    register unsigned char *q ;
  326.  
  327.    if (p == NULL) {
  328.       if (len > 32760)
  329.          error("! oops, raster too big") ;
  330.       if (bytesleft < len) {
  331.          if (RASTERCHUNK > len) {
  332.             raster = (quarterword *)malloc((unsigned)RASTERCHUNK) ;
  333.             bytesleft = RASTERCHUNK ;
  334.          } else {
  335.             raster = (quarterword *)malloc((unsigned)(len + 3)) ;
  336.             bytesleft = len ;
  337.          }
  338.          if (raster == NULL) {
  339.             error("! out of memory during allocation") ;
  340.          }
  341.       }
  342.       p = (unsigned char *)raster ;
  343.       bytesleft -= len ;
  344.       raster += len ;
  345.    }
  346.    q = p ;
  347.    while (len > 0) {
  348.       *p++ = *what++ ;
  349.       len -- ;
  350.    }
  351.    return ((char *)q) ;
  352. }
  353.  
  354. /* Now the main routine, which is called when a character is used
  355.    for the very first time. */
  356.  
  357. repack(cp)
  358. register chardesctype *cp ;
  359. {
  360.    register long i, j ;
  361.    register unsigned char *p ;
  362.    register int width, height ;
  363.    register int wwidth ;
  364.    char startbytes ;
  365.  
  366.    p = cp->packptr ;
  367.    if (p == NULL)
  368.       error("! no raster?") ;
  369.    tsp = tempstore ;
  370.    tsend = tempstore + tslen ;
  371.    addts(*p) ; /* copy the PK flag byte */
  372.    if (*p & 4) {
  373.       if ((*p & 7) == 7) {
  374.          startbytes = 17 ;
  375.          width = getlong(p + 1) ;
  376.          height = getlong(p + 5) ;
  377.          for (i=0; i<12; i++)
  378.             addts(*++p) ;
  379.       } else {
  380.          startbytes = 9 ;
  381.          width = p[1] * 256 + p[2] ;
  382.          height = p[3] * 256 + p[4] ;
  383.          addts(*++p) ;
  384.          addts(*++p) ;
  385.          addts(*++p) ;
  386.          addts(*++p) ;
  387.       }
  388.    } else {
  389.       startbytes = 5 ;
  390.       width = p[1] ;
  391.       height = p[2] ;
  392.    }
  393.    addts(*++p) ;
  394.    addts(*++p) ;
  395.    addts(*++p) ;
  396.    addts(*++p) ;
  397.    p++ ; /* OK, p now points to beginning of the nibbles */
  398.    addts((unsigned char)0) ;
  399.    addts((unsigned char)0) ;
  400.    addts((unsigned char)0) ;
  401.    addts((unsigned char)0) ; /* leave room to stick in a new length field */
  402.    wwidth = (width + 15) / 16 ;
  403.    i = 2 * height * (long)wwidth ;
  404.    if (i <= 0)
  405.       i = 2 ;
  406.    if (mbytesleft < i) {
  407.       if (mbytesleft >= RASTERCHUNK)
  408.          (void) free((char *) mraster) ;
  409.       if (RASTERCHUNK > i) {
  410.          mraster = (quarterword *)malloc((unsigned)RASTERCHUNK) ;
  411.          mbytesleft = RASTERCHUNK ;
  412.       } else {
  413.          mraster = (quarterword *)malloc((unsigned)(i + 3)) ;
  414.          mbytesleft = i ;
  415.       }
  416.       if (mraster == NULL) {
  417.          error("! out of memory during allocation") ;
  418.       }
  419.    }
  420.    while (i > 0)
  421.       mraster[--i] = 0 ;
  422.    i = p - cp->packptr ;
  423.    i += unpack(p, mraster, width, height, *(cp->packptr)) ;
  424.    dochar(mraster, (width + 7) >> 3, height) ;
  425.    j = tsp - tempstore ;
  426. #ifdef DEBUG
  427.    if (dd(D_COMPRESS))
  428. #ifdef SHORTINT
  429.         (void)fprintf(stderr,"PK %ld bytes, unpacked %ld, compressed %ld\n",
  430. #else /* ~SHORTINT */
  431.         (void)fprintf(stderr,"PK %d bytes, unpacked %d, compressed %d\n",
  432. #endif /* ~SHORTINT */
  433.             i-startbytes, ((width+7)/8)*height, j-startbytes-4) ;
  434. #endif /* DEBUG */
  435.    if ( i < j )
  436.       cp->packptr = (unsigned char *)makecopy(tempstore, j, NULL) ;
  437.    else
  438.       makecopy(tempstore, j, cp->packptr) ;
  439.    putlong(cp->packptr + startbytes, j - startbytes - 4) ;
  440.    cp->flags |= REPACKED ;
  441. }
  442.  
  443. putlong(a, i)
  444. register char *a ;
  445. long i ;
  446. {
  447.    register char *b = (char *)&i ;
  448.  
  449.    a[0] = b[0] ;
  450.    a[1] = b[1] ;
  451.    a[2] = b[2] ;
  452.    a[3] = b[3] ;
  453. }
  454.  
  455. long getlong(a)
  456. register char *a ;
  457. {
  458.    long t ;
  459.    register char *b ;
  460.  
  461.    b = (char *)&t ;
  462.    b[0] = a[0] ;
  463.    b[1] = a[1] ;
  464.    b[2] = a[2] ;
  465.    b[3] = a[3] ;
  466.    return(t) ;
  467. }
  468.